package c01_array;

/**
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * 输入: [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出: 6
 */
public class S42 {
    public static void main(String[] args) {
        S42 s42 = new S42();
      int[] arr = new int[]{0,1,0,2,1,0,1,3,2,1,2,1};
        //    int[] arr = new int[]{2,0,2};
        int trap = s42.trap(arr);
        System.out.println(trap);
    }
    public int trap(int[] height) {
        if(height.length<2) return 0;
        int totalTrap = 0;
        int left = 0;
        int right=0;
        int maxIndexLeft = findMaxLeft(height);
        if(height[maxIndexLeft]==0) {
            return 0;
        }
        int maxIndexRight = findMaxRight(height);
        //1. 处理左边问题
        left = 0;
        //1.1 跳过0起点
        while(height[left]==0) {
            left++;
        }
        for (int i = left+1; i <= maxIndexLeft; i++) {
            if(height[i]<height[left]) {
                continue;
            }else {
                for(int j = left+1;j<i;j++) {
                    totalTrap+=height[left]-height[j];
                }
                left=i;
            }
        }
        //2. 处理中间问题
        for (int i = maxIndexLeft; i <= maxIndexRight; i++) {
            totalTrap+=height[maxIndexLeft]-height[i];
        }
        //3. 处理右边问题
        right =height.length-1;
        // 3.1 跳过0起点
        while(height[right]==0) {
            right--;
        }
        for (int i = right-1; i >= maxIndexRight; i--) {
            if(height[i]<height[right]) {
                continue;
            }else {
                for(int j = right-1;j>i;j--) {
                    totalTrap+=height[right]-height[j];
                }
                right=i;
            }
        }
        return totalTrap;
    }
    public int findMaxLeft(int[] height) {
        int max = Integer.MIN_VALUE;
        int maxIndex =0;
        for (int i = 0; i < height.length; i++) {
            if(height[i]>max) {
                max=height[i];
                maxIndex=i;
            }
        }
        return maxIndex;
    }
    public int findMaxRight(int[] height) {
        int max = Integer.MIN_VALUE;
        int maxIndex =height.length-1;
        for (int i = height.length-1; i >=0; i--) {
            if(height[i]>max) {
                max=height[i];
                maxIndex=i;
            }
        }
        return maxIndex;
    }
}
